import java.util.*;

public class BinaryTree1 {
    //判断是否是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        Queue<TreeNode>queue=new LinkedList<>();
        if(root==null){
            return true;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            else{
                break;
            }
        }
        while(!queue.isEmpty()){
            TreeNode tem=queue.peek();
            if(tem!=null){
                return false;
            }
            else{
                queue.poll();
            }
        }return true;
    }
    //前序遍历
    //遍历思路
    public void preorderTraversal(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+' ');
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
    //子问题思路
    public List<Character> preorderTraversal1(TreeNode root){
        List<Character>relist=new ArrayList<>();
        if(root==null){
            return relist;
        }
        relist.add(root.val);
        List<Character>leftTree=preorderTraversal1(root.left);
        relist.addAll(leftTree);
        List<Character>rightTree=preorderTraversal1(root.right);
        relist.addAll(rightTree);
        return relist;
    }
    //中序遍历
    //遍历思路
    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        preorderTraversal(root.left);
        System.out.print(root.val+" ");
        preorderTraversal(root.right);
    }
    //子问题思路
    public List<Character>inOrder1(TreeNode root){
        List<Character>relist=new ArrayList<>();
        if(root==null){
            return relist;
        }
        List<Character>leftTree=inOrder1(root.left);
        relist.addAll(leftTree);
        relist.add(root.val);
        List<Character>rightTree=inOrder1(root.right);
        relist.addAll(rightTree);
        return relist;
    }
    //后序遍历
    public void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        System.out.println(root.val);
    }
    //求树的节点个数
    //遍历思路
    public int count=0;
    public int size(TreeNode root){
        if(root==null){
            return 0;
        }
        count++;
        size(root.left);
        size(root.right);
        return count;
    }
    //子问题思路
    public int size1(TreeNode root){
        if(root==null){
            return 0;
        }
        return size1(root.left)+size1(root.right)+1;
    }
    public int leftCount=0;
    //求叶子结点的个数
    //遍历思路
    public void getleftCount(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leftCount++;
        }
        getleftCount(root.left);
        getleftCount(root.right);
    }
    //子问题思路
    public int getLeftCount1(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeftCount1(root.left)+getLeftCount1(root.right);
    }
    //获取第k层结点个数
    //子问题思路
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
    //查找结点
    public TreeNode find(TreeNode root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode ret=find(root.left,val);
        if(ret!=null){
            return ret;
        }
        ret=find(root.right,val);
        if(ret!=null){
            return ret;
        }
        return null;
    }
    //两棵树是不是相同的二叉树
    public boolean isSameTree(TreeNode p,TreeNode q){
        if(p!=null&&q==null){
            return false;
        }
        if(p==null&&q!=null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //求一棵树是不是另外一棵树的子树
    public boolean isSubtree(TreeNode root,TreeNode subRoot){
        if(root==null||subRoot==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    public int height(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=height(root.left);
        int rightHeight=height(root.right);
        return Math.max(leftHeight+1,rightHeight+1);
    }
    public boolean isBalanced(TreeNode root){
        if(root==null){
            return true;
        }
        int left=height(root.left);
        int right=height(root.right);
        return Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
    //判断是不是对称二叉树
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree==null&&rightTree!=null){
            return false;
        }if(leftTree!=null&&rightTree==null){
            return false;
        }
        if(leftTree==null&&rightTree==null){
            return true;
        }
        if(leftTree.val!=rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
    }
    public boolean isSymmetric(TreeNode root){
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }

    //层序遍历二叉树
    public List<List<Integer>>levelOrder(TreeNode root){
        List<List<Integer>>ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode>queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            List<Integer>list=new ArrayList<>();
            while(size!=0){
                TreeNode cur=queue.poll();
                //list.add(cur.val);在oj写的时候哟放开注释
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNextLine()){
            String str=scanner.nextLine();
            TreeNode root=createTree(str);
            inOrder3(root);
        }
    }
    public static int i=0;
    public static TreeNode createTree(String str){
       TreeNode root=null;
      if(str.charAt(i)!='#'){
           root=new TreeNode(str.charAt(i));
           i++;
           root.left=createTree(str);
           root.right=createTree(str);
       }
       else{
           i++;
        }
       return root;
    }
    public static void inOrder3(TreeNode root){
        if(root==null){
            return;
        }
        inOrder3(root.left);
        System.out.print(root.val+' ');
        inOrder3(root.right);
    }

}
